This invention relates generally to avoiding congestion in computer networks, and more particularly to limiting a transmission rate of end stations in order to avoid congestion at intermediate links.
As computer networks become increasingly more complex, more and more end stations communicate through more and more intermediate links. An intermediate link is typically a section of network cable with nodes or network switches at each end of the cable. A link can carry only a predetermined amount of network traffic, usually expressed as a bit per second limit. Network traffic is typically referred to as packets or cells, and each packet or cell requires a number of bits to be transmitted over the network.
For example, an intermediate link may carry traffic originating at numerous source end stations. And each source end station may be capable of generating network traffic at a rate in excess of what the intermediate link can handle without dropping packets. That is, each individual end station may be capable of driving an intermediate link into congestion. Accordingly, when a plurality of end stations are creating network traffic, and all of that traffic passes through a particular intermediate link, it is clear that a mechanism must be installed to limit the traffic created by the source end stations. Flow control is the generic term used to describe a mechanism to limit traffic created by source end stations.
Fairness in allocation of link capacity to various source end stations is another consideration which flow control must address. If one source end station uses the entire capacity of an intermediate link, then no other source end station can transmit. Congestion management systems provide each source end station with an opportunity to transmit, even though transmissions are at a rate reduced from what the source end station desires.
In many networks, particularly connection oriented networks, substantially stable routes are established for transfer of packets from a selected source end station to a selected destination end station. Typically, such stable routes are referred to as sessions or as virtual circuits. A virtual circuit is a path through intermediate links and nodes between a designated source end station and a designated destination end station. Each packet carries a designation of the virtual circuit, and each intermediate node maintains state information so that it can examine the virtual circuit designation in a received packet and accordingly forward the packet onto an appropriate downstream link.
Two common types of flow control typically utilized in networks having stable routes such as virtual circuits are, firstly, end-to-end flow control, and secondly, hop-by-hop flow control.
End-to-end flow control typically has a destination end station detect that congestion is occurring in the network. A destination end station may detect congestion by an intermediate node inserting a flag into a forwarded packet, where the flag informs the destination end station that the intermediate node""s buffers are filling or that the intermediate node is otherwise experiencing congestion. The destination end station then places congestion information in an acknowledgement packet returned to the source end station, and the source end station reacts to the congestion information by reducing the rate which the source end station transmits packets onto the network.
A further refinement of end-to-end flow control is to transfer control packets along a virtual circuit from a source station, through the network to a destination station, and in response the destination station returns the control packet to the source station along the virtual circuit. As the control packet passes through the network, link capacity information is written into the control packet as it passes through each link of the virtual circuit. Each node at each link along the virtual circuit then maintains a table giving transmission rate information pertaining to each virtual circuit passing through that node.
Problems with a method of computing a transmission rate for each virtual circuit is that each intermediate node must keep a table containing state information for each virtual circuit passing through. Further, when a change occurs in the network, such as a new virtual circuit is established or an old virtual circuit is dropped, the network must respond rapidly to the change. Response to a change, in past attempts to apply end-to-end flow control, require a convergence time which is too long. For example, the worst case convergence time in many past systems is proportional to the number of virtual circuits, in addition to the dominant (or maximum) round trip time. Such long convergence times are not acceptable for efficient congestion management.
Secondly, hop-by-hop flow control is next discussed. In hop-by-hop flow control a downstream node uses a mechanism to inform an immediate upstream node to limit the rate at which the upstream node transmits packets to the downstream node. A typical mechanism used by the downstream node to limit the rate at which packets are transmitted by the upstream node, is the issuance of credits. Credits issued by the downstream node reflect the number of buffers in the downstream node. Credit information is sent in a control packet to the upstream node. The upstream node is permitted to send only the number of packets for which it has credits, and the upstream node decrements its credit count as it sends a packet. When the downstream node receives a packet the packet is stored in a buffer, and later the buffer is drained by the downstream node further processing the packet. As packets are forwarded by the downstream node, the downstream node sends credit information to the upstream node. Accordingly, the upstream node receives and uses credits to control the rate at which it transmits packets (or cells) to the downstream node. All of the nodes in the network use the hop-by-hop credit based flow control, and so permit their source stations to send only the number of packets which each node can handle.
Hop-by-hop flow control has been implemented by using either static buffering or dynamic buffering. In static buffering, sufficient buffers for each virtual circuit to fully occupy each link must be provided. Each individual virtual circuit may be capable of fully using the capacity of an intermediate link. Accordingly, each virtual circuit must have enough buffers assigned for it to fully use the capacity of the link. When many virtual circuits are established, the number of buffers needed becomes excessive. For example, in a transmission protocol referred to as Asynchronous Transfer Mode, or ATM, there are 24 bits assigned to designate a virtual circuit. Accordingly the number of possible virtual circuits is 224. It is not practical to provide buffering at full link capacity for so many virtual circuits. And one never knows which of these virtual circuits will require buffering at full link capacity.
Secondly, when dynamic buffering is used, in a particular intermediate node, a pool of buffers is assigned for all of the virtual circuits passing through that node. Some of the buffers are allocated to each virtual circuit as they are needed. A problem is that when the network changes by adding or subtracting a virtual circuit, the system is very slow in responding to the change. For example, when a new virtual circuit is added, there may be no buffers available to be assigned to the new virtual circuit, as they may already be full from their previous assignment. The buffers drain slowly. Accordingly, the new virtual circuit must wait for a long time before it can begin transmission. Such long waits are unacceptable in efficient network management.
There is needed a flow control system capable of scaling to a large number of virtual circuits, capable of responding quickly to a change in the number of established virtual circuits, capable of responding to the different requirements of many different source end stations, and capable establishing a fair allocation of network resources to all of the source end stations.
A system for controlling a transmission rate of a source station on a computer network has: a control cell transmitter for transmitting a control cell onto the computer network, the control cell travelling in an established virtual circuit, the control cell having a stamped transmission rate written into a stamped rate field, and having a control u_bit value written into a u_bit field; a selector in a network switch to select a fair transmission rate for the virtual circuit; a receiver in a network switch to receive the control cell on an incoming link of the network, and for reading the stamped transmission rate and the u_bit value; a processor in a network switch to write a new stamped transmission rate into the stamped rate field of the control cell before transmitting the control cell onto the outgoing link, the new stamped transmission rate computed in response to the received stamped rate and the fair transmission rate, and for writing a value into the u_bit field of the outgoing control cell to indicate whether the new stamped transmission rate differs from the received stamped rate; a receiver in a destination station to receive the control cell and to send a return cell containing a value received by the destination station in the stamped rate field and in the u_bit field; a receiver in the source station to receive the return cell and to read a returned stamped rate and a returned u_bit value; transmission rate controller in the source station to set a new rate for transmission of a plurality of data cells by the apparatus in response to the returned stamped rate and the returned u_bit value. The system implements the above method by a global timing means located in each source station and in each switch for timing events, to time in a source station sending of one control cell for each virtual circuit established in the source station and to time in a switch the calculation of a fair transmission rate; and by discrete transmission rate generating means for calculating a plurality of permitted discrete transmission rates, and for requiring that all stamped transmission rates written into the control cell and all fair transmission rates are selected as one rate of the plurality of permitted discrete transmission rates. The system further maintains state information in each switch such that only the plurality of permitted discrete transmission rates and the number of source end stations transmitting at each permitted discrete transmission rate are maintained. Thus the system alleviates the need to maintain functionally equivalent state information in each switch on a per virtual circuit basis.
A system for selecting transmission rates for a plurality of source stations having: selection means for establishing a feasible transmission rate for each source station on all established virtual circuits, the feasible rates defined as a transmission rate for each source station such that the sum of all transmission rates of all virtual circuits passing through a link do not exceed the capacity of the link, for all links in the network; means for allocating available buffers among virtual circuits passing through the link; means for allocating buffers to the virtual circuits such that the proportions of allocated buffers are equal to the proportions of the feasible transmission rates of the virtual circuits; and having hop-by-hop flow control means for dynamically allocating buffers in a network switch to permit the source stations to transmit data cells at a transmission rate in excess of the feasible transmission rates.
These and other features and advantages of the present invention will become apparent from a reading of the detailed description in conjunction with the attached drawings in which like reference numerals refer to like elements in the several views.